Algorithms and Abstract Data Types

The main program initialises all the elements in QueueData to a suitable null value, QueueHead to -1 and QueueTail to -1.

Write program code for the main program.

Save your program as Question3_J24.

Copy and paste the program code into part 3(a) in the evidence document.

The function Enqueue() takes the data to insert into the queue as a parameter.

If the queue is not full, it inserts the parameter in the queue, updates the appropriate pointer(s) and returns TRUE. If the queue is full, it returns FALSE.

Write program code for Enqueue().

Save your program.

Copy and paste the program code into part 3(b) in the evidence document.

The function Dequeue() returns "false" if the queue is empty. If the queue is not empty, it returns the next item in the queue and updates the appropriate pointer(s).

Write program code for Dequeue().

Save your program.

Copy and paste the program code into part 3(c) in the evidence document.

The subroutine StoreItems() takes ten 7-character strings as input from the user and uses the check digit to validate each input.

Each valid input has the check digit removed and is stored in the queue using Enqueue().

An appropriate message is output if the item is inserted. An appropriate message is output if the queue is already full.

Invalid inputs are not stored in the queue.

The subroutine counts and outputs the number of invalid items that were entered.

StoreItems() can be a procedure or a function as appropriate.

Write program code for StoreItems().

Save your program.

Copy and paste the program code into part 3(d)(i) in the evidence document.

Write program code to amend the main program to:

• call StoreItems()
• call Dequeue()
• output a suitable message if the queue was empty
• output the returned value if the queue was not empty.

Save your program.

Copy and paste the program code into part 3(d)(ii) in the evidence document.

Test the program with the following inputs in the order given:

999999X
1251484
5500212
0033585
9845788
6666666
3258746
8111022
7568557
0012353

Take a screenshot of the output(s).

Save your program.

Copy and paste the screenshot into part 3(d)(iii) in the evidence document.

Write program code to declare the record structure Queue and its fields.

If your programming language does not support record structures, a class can be declared instead.

If you are writing in Python, use comments to declare the appropriate data types.

Save your program as Question2_N24.

Copy and paste the program code into part 2(a) in the evidence document.

The main program creates a new Queue record with the identifier TheQueue. The head pointer is initialised to –1. The tail pointer is initialised to 0. Each element in the array is initialised with –1.

Write program code for the main program.

Save your program.

Copy and paste the program code into part 2(b) in the evidence document.

The pseudocode function Enqueue() inserts an integer value into the queue.

The function is incomplete. There are three incomplete statements.

FUNCTION Enqueue(BYREF AQueue : Queue, BYVAL TheData : INTEGER) 
 RETURNS INTEGER
 IF AQueue.Headpointer = -1 THEN
    AQueue.QueueArray[AQueue.Tailpointer] ← ........................................
    AQueue.Headpointer ← 0
    AQueue.Tailpointer ← AQueue.Tailpointer + 1
    RETURN 1
 ELSE
    IF AQueue.Tailpointer > ........................................ THEN
       RETURN -1
    ELSE
       AQueue.QueueArray[AQueue.Tailpointer] ← TheData
       AQueue.Tailpointer ← AQueue.Tailpointer ........................................
       RETURN 1
    ENDIF
 ENDIF
ENDFUNCTION

Write program code for Enqueue().

Save your program.

Copy and paste the program code into part 2(c) in the evidence document.

The function ReturnAllData() accesses TheQueue. It concatenates all the integer values that have been inserted into the queue’s array, starting from the value stored at HeadPointer, with a space between each integer value. The string of concatenated values is returned.

None of the integer values are removed from the queue.

Write program code for ReturnAllData().

Save your program.

Copy and paste the program code into part 2(d) in the evidence document.

The main program asks the user to enter 10 integers with values of 0 or greater. It reads each input repeatedly until a valid number is entered.

All 10 valid inputs are added to the queue, using Enqueue().

If the value returned from Enqueue() is –1, a message is output to state that the queue is full, otherwise a message is output to state that the item has been added to the queue.

The function ReturnAllData() is called once all 10 integers have been entered and the return value from the function call is output.

Amend the main program to perform these actions.

Save your program.

Copy and paste the program code into part 2(e)(i) in the evidence document.

Test your program with the following inputs in the order given:

10 9 –1 8 7 6 5 4 3 2 1

Take a screenshot of the output.

Save your program.

Copy and paste the screenshot into part 2(e)(ii) in the evidence document.

The function Dequeue() accesses TheQueue. The function returns –1 if the queue is empty. If the queue is not empty, the function returns the next item in the queue and updates the relevant pointer(s).

The data is not replaced or deleted from the queue.

Write program code for Dequeue().

Save your program.

Copy and paste the program code into part 2(f) in the evidence document.

The main program calls Dequeue() twice, and each time it either outputs ‘Queue empty’ if there is no data in the queue or outputs the return value.

The main program then calls ReturnAllData() a second time.

Amend the main program.

Save your program.

Copy and paste the program code into part 2(g)(i) in the evidence document.

Test your program with the following inputs in the order given:

10 9 8 7 6 5 4 3 2 1

Take a screenshot of the output.

Save your program.

Copy and paste the screenshot into part 2(g)(ii) in the evidence document.

Write program code to:

• declare the global 2D array ArrayNodes
• initialise all 3 integer values to –1 for each node.

Save your program as Question3_N22.

Copy and paste the program code into part 3(a) in the evidence document.

The binary tree stores the following values:

FreeNode stores the index of the first free element in the array, initialised to 6.

RootPointer stores the index of the first node in the tree, initialised to 0.

Amend your program by writing program code to store the given data in ArrayNodes and initialise the free node and root node pointers.

Save your program.

Copy and paste the program code into part 3(b) in the evidence document.

The following recursive pseudocode function searches the binary tree for a given value. If the value is found, the function must return the index of the value. If the value is not found, the function must return –1.

The function is incomplete. There are four incomplete statements.

FUNCTION SearchValue(Root : INTEGER, 
                     ValueToFind : INTEGER) RETURNS INTEGER
   IF Root = –1 THEN
      RETURN –1
   ELSE
      IF ArrayNodes[Root, 1] = ValueToFind THEN
         RETURN .......................................
      ELSE
         IF ArrayNodes[Root, 1] = –1 THEN
            RETURN –1
         ENDIF
      ENDIF
   ENDIF
   IF ArrayNodes[Root, 1] ....................................... ValueToFind THEN
      RETURN SearchValue(ArrayNodes[............, 0], ValueToFind)
   ENDIF
   IF ArrayNodes[Root, ............] < ValueToFind THEN
      RETURN SearchValue(ArrayNodes[Root, 2], ValueToFind)
   ENDIF
ENDFUNCTION

Write program code for the function SearchValue().

Save your program.

Copy and paste the program code into part 3(c) in the evidence document.

A post order traversal performs the following operation:

• visit the left node
• visit the right node
• output the root.

For example, in the following tree, the output would be: 3 9 25 60 50

An outline of the PostOrder() procedure is:

• If left node is not empty, make a recursive call with the left node as the root.
• If right node is not empty, make a recursive call with the right node as the root.
• Output the current root node.

The procedure PostOrder() takes the root node as a parameter.

Write program code for the procedure PostOrder().

Save your program.

Copy and paste the program code into part 3(d) in the evidence document.

Amend the main program by writing program code to:

• call the function SearchValue() to find the position of the number 15 in the tree
• use the result from SearchValue() to output either the index of the value if found, or an appropriate message to state that the value was not found
• call the procedure PostOrder().

Save your program.

Copy and paste the program code into part 3(e)(i) in the evidence document.

Test your program.

Take a screenshot to show the output.

Copy and paste the screenshot into part 3(e)(ii) in the evidence document.

The program contains the following global arrays and variables:

• 1D array Animal to store the names of up to 20 animals.
• 1D array Colour to store the names of up to 10 colours.
• AnimalTopPointer to point to the next free space in the array Animal, initialised to 0.
• ColourTopPointer to point to the next free space in the array Colour, initialised to 0.

Write program code to declare the global arrays and variables.

Save your program as Question3_J2023.

Copy and paste the program code into part 3(a) in the evidence document.

Study the pseudocode function PushAnimal():

FUNCTION PushAnimal(DataToPush : STRING) RETURNS BOOLEAN
   IF AnimalTopPointer = 20 THEN
      RETURN FALSE
   ELSE
      Animal[AnimalTopPointer] ← DataToPush
      AnimalTopPointer ← AnimalTopPointer + 1
      RETURN TRUE
   ENDIF
ENDFUNCTION

Write program code for the function PushAnimal()

Save your program.

Copy and paste the program code into part 3(b)(i) in the evidence document.

Study the pseudocode function PopAnimal():

FUNCTION PopAnimal() RETURNS STRING
   DECLARE ReturnData : STRING
   IF AnimalTopPointer = 0 THEN
      RETURN ""
   ELSE
      ReturnData ← Animal[AnimalTopPointer - 1]
      AnimalTopPointer ← AnimalTopPointer - 1
      RETURN ReturnData
   ENDIF
ENDFUNCTION

Write program code to declare the function PopAnimal()

Save your program.

Copy and paste the program code into part 3(b)(ii) in the evidence document.

The procedure ReadData():

• reads the animal names from the file AnimalData.txt
• uses PushAnimal() to insert each name onto the stack
• uses appropriate exception handling if the file does not exist.

Write program code for the procedure ReadData()

Save your program.

Copy and paste the program code into part 3(b)(iii) in the evidence document.

The function PushColour() performs the same actions as PushAnimal() but inserts an item into Colour.

The function PopColour() performs the same actions as PopAnimal() but removes the next item from Colour.

Write program code for the functions PushColour() and PopColour()

Save your program.

Copy and paste the program code into part 3(b)(iv) in the evidence document.

Amend the procedure ReadData() so that it also:

• reads the colours from the text file ColourData.txt
• uses PushColour() to insert each colour onto the stack
• uses appropriate exception handling if the file does not exist.

Save your program.

Copy and paste the program code into part 3(b)(v) in the evidence document.

The procedure OutputItem():

• pops the next item from both Animal and Colour
• outputs the colour and animal on one line, for example "black horse"

If there is no data in Colour:

• the animal is pushed back onto Animal
• "No colour" is output.

If there is no data in Animal:

• the colour is pushed back onto Colour
• "No animal" is output.

Write program code for the procedure OutputItem()

Save your program.

Copy and paste the program code into part 3(c) in the evidence document.

Test your program.

Take a screenshot of the output.

Save your program.

Copy and paste the screenshot into part 3(d)(ii) in the evidence document.

Write program code to declare Stack, initialise each element in the array with a null value and declare and initialise TopOfStack

Save your program as Question1_N25.

Copy and paste the program code into part 1(a) in the evidence document.

The function Push() takes an integer parameter. If the stack is full, the function returns FALSE. If the stack is not full, the parameter is inserted into the stack, the pointer is updated and the function returns TRUE

Write the program code for Push()

Save your program.

Copy and paste the program code into part 1(b) in the evidence document.

The function Pop() returns the next integer in the stack and updates the pointer as appropriate. If there is no data in the stack, the function returns the value –999

Write the program code for Pop()

Save your program.

Copy and paste the program code into part 1(c) in the evidence document.

The main program generates 40 random integers between 0 and 1000 (inclusive) and attempts to insert each one into the stack using the appropriate function. If the return value from the function call indicates the stack is full, no more integers are generated and "Stack full" is output.

Write program code for the main program.

Save your program.

Copy and paste the program code into part 1(d) in the evidence document.

The procedure FindValues():

• pops each integer from the stack until the stack is empty
• finds and outputs the largest number that was in the stack in an appropriate message
• finds and outputs the smallest number that was in the stack in an appropriate message.

Write program code for FindValues()

Save your program.

Copy and paste the program code into part 1(e) in the evidence document.

Test your program.

Take a screenshot of the output(s).

Save your program.

Copy and paste the screenshot(s) into part 1(f)(ii) in the evidence document.

The function Enqueue() takes the data to insert into the queue as a parameter.

If the queue is not full, it inserts the parameter in the queue, updates the appropriate pointer(s) and returns TRUE. If the queue is full, it returns FALSE.

Write program code for Enqueue().

Save your program.

Copy and paste the program code into part 3(b) in the evidence document.

The function Dequeue() returns "false" if the queue is empty. If the queue is not empty, it returns the next item in the queue and updates the appropriate pointer(s).

Write program code for Dequeue().

Save your program.

Copy and paste the program code into part 3(c) in the evidence document.

The subroutine StoreItems() takes ten 7-character strings as input from the user and uses the check digit to validate each input.

Each valid input has the check digit removed and is stored in the queue using Enqueue().

An appropriate message is output if the item is inserted. An appropriate message is output if the queue is already full.

Invalid inputs are not stored in the queue.

The subroutine counts and outputs the number of invalid items that were entered.

StoreItems() can be a procedure or a function as appropriate.

Write program code for StoreItems().

Save your program.

Copy and paste the program code into part 3(d)(i) in the evidence document.

Write program code to amend the main program to:

• call StoreItems()
• call Dequeue()
• output a suitable message if the queue was empty
• output the returned value if the queue was not empty.

Save your program.

Copy and paste the program code into part 3(d)(ii) in the evidence document.

Test the program with the following inputs in the order given:

999999X
1251484
5500212
0033585
9845788
6666666
3258746
8111022
7568557
0012353

Take a screenshot of the output(s).

Save your program.

Copy and paste the screenshot into part 3(d)(iii) in the evidence document.

Write program code to:

• declare a global array, CircularQueue, of 5 items to store the sale records
• declare the global pointers Head and Tail
• declare the global variable NumberOfItems
• initialise all elements of the array CircularQueue to an empty record, where the ID is null ("") and quantity is -1
• initialise Head, Tail and NumberOfItems to 0

Save your program.

Copy and paste the program code into part 2(b) in the evidence document.

The function Enqueue():

• takes a new record as a parameter
• inserts the record in the circular queue at the element pointed to by Tail
• updates pointers and other variables as required
• returns -1 if the circular queue is full
• returns 1 if the record is stored successfully.

Write program code for the function Enqueue().

Save your program.

Copy and paste the program code into part 2(c) in the evidence document.

The function Dequeue():

• returns a null or empty record if the circular queue is empty
• returns the first record in the queue if the circular queue is not empty
• updates pointers and other variables as required.

Write program code for the function Dequeue().

Save your program.

Copy and paste the program code into part 2(d) in the evidence document.

The procedure EnterRecord():

• takes an ID and quantity as input and creates a sale record
• uses Enqueue() to insert the record in the circular queue
• outputs "Full" if the record was not inserted in the circular queue
• outputs "Stored" if the record was inserted in the circular queue.

Write program code for the procedure EnterRecord().

Save your program.

Copy and paste the program code into part 2(e) in the evidence document.

Amend the main program to:

• use EnterRecord() to input the six records in the table
• use Dequeue() to remove one record
• output either the ID and quantity of the removed record, or an error message if the circular queue is empty
• use EnterRecord() to input the record with the ID "LLP" for a second time
• output the ID and quantity for all the records currently stored in the array CircularQueue.

Write program code to perform these tasks.

Save your program.

Copy and paste the program code into part 2(f)(i) in the evidence document.

Test your program.

Take a screenshot of the output.

Save your program.

Copy and paste the screenshot into part 2(f)(ii) in the evidence document.

Write program code to declare and initialise Queue, QueueHead, QueueTail and NumberItems

Save your program as Question2_N25.

Copy and paste the program code into part 2(a) in the evidence document.

The function Enqueue() takes a string as a parameter. The function checks if the queue is full, and returns Boolean FALSE if the queue is full.

If the queue is not full, the parameter is inserted into the next position in Queue. The function updates the appropriate pointer(s), updates NumberItems and then returns Boolean TRUE

Write program code for Enqueue()

Save your program.

Copy and paste the program code into part 2(b) in the evidence document.

The function Dequeue() returns the string "False" if the queue is empty.

If the queue is not empty, the function returns the next element in the queue. The function updates the appropriate pointer(s) and updates NumberItems

Write program code for Dequeue()

Save your program.

Copy and paste the program code into part 2(c) in the evidence document.

The text file BinaryData.txt stores individual binary digits, '1' and '0'. Each digit is on a new line. For example, the first line in the text file stores '1', the second line stores '1'

The procedure ReadData() reads in each line from the text file BinaryData.txt and inserts it into the queue using the appropriate method.

The procedure needs to work for a text file with any number of lines up to a maximum of 100.

Write program code for ReadData()

Save your program.

Copy and paste the program code into part 2(d) in the evidence document.

The string data in the text file is compressed.

The compression algorithm counts the number of times each binary digit appears consecutively, then stores the binary digit followed by the number of times it appears. The algorithm stores the compressed data in a single string.

For example, if the text file contains the data:

1
1
0
0
0
1
1
1

The compression algorithm will create the string "120313" because there are two '1' digits, followed by three '0' digits, followed by three '1' digits.

The procedure Compress() uses Dequeue() to remove each element from the queue in turn. The procedure then compresses the data following the compression algorithm described. The new compressed string is stored in the global variable NewString

You can assume that one binary digit will never appear more than nine times consecutively in the sequence.

You can assume that there will always be at least one item in the queue.

Write program code for Compress()

Save your program.

Copy and paste the program code into part 2(e) in the evidence document.

Test your program.

Take a screenshot of the output(s).

Save your program.

Copy and paste the screenshot(s) into part 2(f)(ii) in the evidence document.

Write program code for the main program.

Declare a 1D array of type node with the identifier linkedList, and initialise it with the data shown in the table on page 2. Declare the pointers.

Save your program.

Copy and paste the program code into part 1(b) in the evidence document.

Write program code for the procedure outputNodes().

Save your program.

Copy and paste the program code into part 1(c)(i) in the evidence document.

Edit the main program to call the procedure outputNodes().

Take a screenshot to show the output of the procedure outputNodes().

Save your program.

Copy and paste the screenshot into part 1(c)(ii) in the evidence document.

Write program code for the function addNode().

Save your program.

Copy and paste the program code into part 1(d)(i) in the evidence document.

Edit the main program to:

• call addNode()
• output an appropriate message depending on the result returned from addNode()
• call outputNodes() twice; once before calling addNode() and once after calling addNode().

Save your program.

Copy and paste the program code into part 1(d)(ii) in the evidence document.

Test your program by inputting the data value 5 and take a screenshot to show the output.

Save your program.

Copy and paste the screenshot into part 1(d)(iii) in the evidence document.

Write program code for the main program.

Declare a 1D array of type node with the identifier linkedList, and initialise it with the data shown in the table on page 2. Declare the pointers.

Save your program.

Copy and paste the program code into part 1(b) in the evidence document.

Write program code for the procedure outputNodes().

Save your program.

Copy and paste the program code into part 1(c)(i) in the evidence document.

Edit the main program to call the procedure outputNodes().

Take a screenshot to show the output of the procedure outputNodes().

Save your program.

Copy and paste the screenshot into part 1(c)(ii) in the evidence document.

Write program code for the function addNode().

Save your program.

Copy and paste the program code into part 1(d)(i) in the evidence document.

Edit the main program to:

• call addNode()
• output an appropriate message depending on the result returned from addNode()
• call outputNodes() twice; once before calling addNode() and once after calling addNode().

Save your program.

Copy and paste the program code into part 1(d)(ii) in the evidence document.

Test your program by inputting the data value 5 and take a screenshot to show the output.

Save your program.

Copy and paste the screenshot into part 1(d)(iii) in the evidence document.